package cm.unit3.theme4;

import cm.commom.ListNode;

import java.util.HashMap;
import java.util.Map;

public class EntryNodeOfLoop {

    public ListNode findMeetNode(ListNode pHead){
        if (pHead==null){
            return null;
        }
        // 快指针在前面
        ListNode slowPtr = pHead.next;

        ListNode quickPtr = slowPtr.next;
        while (quickPtr!=null){
            if (quickPtr==slowPtr){
                return quickPtr;
            }
            // 慢指针移动一步
            slowPtr = slowPtr.next;

            // 慢指针移动两步
            quickPtr = quickPtr.next;
            if (quickPtr!=null){
                quickPtr = quickPtr.next;
            }
        }
        return null;
    }

    // 遍历
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode meetNode = findMeetNode(pHead);
        if (meetNode==null){
            return null;
        }
        ListNode pNode = meetNode;
        int nodesInLoop = 1;
        while (pNode.next!=meetNode){
            pNode = pNode.next;
            nodesInLoop++;
        }

        ListNode pNode1 = pHead;
        for (int i = 0; i < nodesInLoop; i++) {
            pNode1 = pNode1.next;
        }
        ListNode pNode2 = pHead;
        while (pNode1!=pNode2){
            pNode1 = pNode1.next;
            pNode2 = pNode2.next;
        }
        return pNode1;
    }

    // 使用hashMap
    public ListNode EntryNodeOfLoop02(ListNode pHead) {

        Map<ListNode,Integer> map = new HashMap<>();
        for (ListNode node=pHead;node!=null;node=node.next){
            if (map.get(node)==null){
                map.put(node,1);
            }else {
                return node;
            }
        }
        return null;
    }
}
